Recent years have seen the beginning of widespread use of three-dimensional graphics. However, applications of these complex graphics are still limited because of the enormous amounts of information required for their implementation. Three-dimensional mesh information representing a three-dimensional model includes geometric information, inter-vertex connectivity information, and property information, such as color, normal, and texture coordinates. The geometric information includes information about three coordinates of a floating point. The connectivity information is represented by an index list in which three or more vertices form one polygon. For example, if a 32 bit floating point is used to represent the geometric information, 96 bits (12 B) are needed to represent single geometric information. That is, a 120 KB memory is required when a three-dimensional mesh model is represented by approximately ten thousand vertices having only the geometric information. A 1.2 MB memory is required when the model is represented by a hundred thousand vertices. Further, since the connectivity information can be overlapped twice or more, a massive memory is required to store a three-dimensional model using a polygonal mesh.
Encoding is needed to solve the problem of the huge amount of information. To this end, a three-dimensional mesh coding (3DMC) scheme adopted as a standard of ISO/IEC (International Organization for Standardization/International Electrotechnical Commission) in the field of MPEG-4 (Moving Picture Expert Group)-SNHC (Synthetic and Natural Hybrid Coding) improves transmission efficiency by encoding/decoding three-dimensional mesh information represented by IndexedFaceSet (IFS) in a Virtual Reality Modeling Language (VRML) file.
FIGS. 1a and 1b respectively illustrate conceptual configurations of conventional 3DMC-based encoding and decoding devices. A 3DMC encoding device 110 includes a topological surgery module 111 for decomposing a three-dimensional mesh model (original model) into two-dimensional mesh structures, a geometric information encoding module 112, a connectivity information encoding module 113, a property information encoding module 114, and an entropy encoding module 115 for collectively compressing encoding results from the encoding modules 112 to 114 to generate a 3DMC bit-stream.
The 3DMC decoding device 120 includes an entropy decoding module 121, a geometric information decoding module 122, a connectivity information decoding module 123, a property information decoding module 124, and a topological synthesis module 125, in order to reconstruct three-dimensional model data from the encoded 3DMC bit-stream.
The 3DMC encoding performed by the above-described 3DMC encoding device 110 includes, as a primary characteristic, a topological surgery operation performed by the topological surgery module 111 to maximize a compression ratio. The topological surgery operation is proposed by IBM cooperation and is a decomposition operation in which a three-dimensional model is decomposed into two-dimensional mesh structures by cutting the model along a given cutting edge on the assumption that a given mesh is the same as a sphere in topological geometry. Such operation results in a simple polygonal graph (e.g., a triangle tree (TT) having a binary tree structure composed of a triangular strip) and a vertex graph (VG) representing a path along which the mesh is cut, as an inter-vertex linked structure.
However, the above-described topological surgery operation may change the order of elements (e.g., vertices and faces) constituting an original model. For this reason, editing cannot be performed in a unit of the elements, such as vertices or faces, and animation effects based on the element order cannot be applied.